package Leetcode

import (
	"fmt"
)

/*
原题：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。*/

func maxProfit(price []int) int {
	if price == nil || len(price) < 1 {
		return 0
	}

	maxPrice := 0

	for i := 0; i < len(price)-1; i++ {
		for j := i + 1; j < len(price); j++ {
			if maxPrice < price[j]-price[i] {
				maxPrice = price[j] - price[i]
			}
		}
	}
	return maxPrice
}

func maxProfit2(price []int) int {
	if price == nil || len(price) < 1 {
		return 0
	}

	max := 0
	min := price[0]

	for i := 1; i < len(price); i++ {
		if min > price[i] {
			min = price[i]
		} else {
			if price[i]-min > max {
				max = price[i] - min
			}
		}
	}
	return max
}

/**
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。
*/

func longestCommonSubsequence(str1, str2 string) int {
	if len(str1) == 0 || len(str2) == 0 {
		return 0
	}

	cell := make([][]int, len(str1))
	for i := 0; i < len(str1); i++ {
		cell[i] = make([]int, len(str2))
	}

	for i, v := range str1 {
		for j, k := range str2 {
			if i == 0 || j == 0 {
				if v == k {
					cell[i][j] = 1
				} else if i == 0 && j > 0 {
					cell[i][j] = cell[i][j-1]
				} else if i > 0 && j == 0 {
					cell[i][j] = cell[i-1][j]
				}
			} else {
				if v == k {
					cell[i][j] = cell[i-1][j-1] + 1
				} else {
					if cell[i-1][j] > cell[i][j-1] {
						cell[i][j] = cell[i-1][j]
					} else {
						cell[i][j] = cell[i][j-1]
					}
				}
			}
		}
	}
	for _, v := range cell {
		fmt.Println(v)
	}
	return cell[len(str1)-1][len(str2)-1]
}

/**
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。
*/

//暴力求解
func maxArea(height []int) int {
	max := 0
	length := len(height)
	for i := 0; i < length; i++ {
		for j := i + 1; j < length; j++ {
			area := min(height[i], height[j]) * (j - i)
			if max < area {
				max = area
			}
		}
	}
	return max
}

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

//双指针法
func maxArea2(height []int) int {
	length := len(height)
	if length < 2 {
		return 0
	}
	i := 0
	j := length - 1
	area, maxarea := 0, 0
	for i < j {
		if height[i] < height[j] {
			area = height[i] * (j - i)
			i++
		} else if height[i] > height[j] {
			area = height[j] * (j - i)
			j--
		} else {
			area = height[i] * (j - i)
			i++
			j--
		}
		if maxarea < area {
			maxarea = area
		}
	}
	return maxarea
}

/** leetcode-64

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28
*/

func UniquePaths(m int, n int) int {
	db := make([][]int, m)
	for i, _ := range db {
		db[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i == 0 || j == 0 {
				db[i][j] = 1
			} else {
				db[i][j] = db[i-1][j] + db[i][j-1]
			}
		}
	}
	return db[m-1][n-1]
}

/**
爬楼梯
*/
func ClimbStairs(n int) int {
	db := make([]int, n)
	for i := 0; i < n; i++ {
		if i == 0 {
			db[i] = 1
			continue
		}
		if i == 1 {
			db[i] = 2
			continue
		}
		db[i] = db[i-1] + db[i-2]
	}
	return db[n-1]
}

/**
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

链接：https://leetcode-cn.com/problems/two-sum
*/
func twoSum(nums []int, target int) []int {
	db := make([]int, 2)
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				db[0] = i
				db[1] = j
				return db
			}
		}
	}
	return db
}

// 斐波拉数量非递归实现, 时间复杂度O(n-2)
func FeiBoLa(n int) {
	num := make([]int, n)
	for i := 0; i < n; i++ {
		if i == 0 || i == 1 {
			num[i] = 1
		} else {
			num[i] = num[i-1] + num[i-2]
		}
	}
	for _, v := range num {
		fmt.Println(v)
	}
}

// 找出数组中不重复的数字
func FindNotRepetitionNum(nums []int) {
	m := make(map[int]int)
	for _, i := range nums {
		m[i]++
	}
	for k, v := range m {
		if v == 1 {
			fmt.Println(k)
		}
	}
}

// 删除数组中重复的数字
func removeDuplicates(nums []int) []int {
	left, right := 0, 1
	for right < len(nums) {
		if nums[left] != nums[right] {
			nums[left+1] = nums[right]
			left++
		}
		right++

	}
	return nums[:left+1]
}

/**
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
*/
func maxProfit3(prices []int) int {
	max := 0
	for i := 0; i < len(prices)-1; i++ {
		t := prices[i+1] - prices[i]
		if t > 0 {
			max = max + t
		}

	}
	return max
}

// 计算回文数数量
func huiWen(str string) {
	if len(str) == 0 {
		return
	}
	count := 0
	db := make([][]string, len(str))
	for i, _ := range db {
		db[i] = make([]string, len(str))
	}

	for i := 0; i < len(str); i++ {
		for j := 0; j <= i; j++ {
			if str[i] == str[j] && (i-j <= 2 || db[i-1][j+1] != "") {
				if i == j {
					db[i][j] = string(str[j])
				} else if i > j {
					db[i][j] = str[j : i+1]
				}
				count++
			}
		}
	}
	for _, a := range db {
		fmt.Println(a)
	}
	fmt.Println(count)
}
